//
// BitArray.h
// Usage: 
//    An unordered array that holds its contents internally as bits. Therefore,
//    each element can only be of boolean type.
//
// Author: James Molloy <james@jamesmolloy.co.uk>, (C) 2007
//
#ifndef _BITARRAY_H_
#define _BITARRAY_H_

#define INDEX_FROM_BIT(a) (a/(8*4))
#define OFFSET_FROM_BIT(a) (a%(8*4))

class BitArray
{
public:
  /**
    Constructor
  **/
  BitArray(int n) :
    N(n)
  {
    table = new int[INDEX_FROM_BIT(N)];
    clearAll();
  }
  
  /**
    Clears the value of all bits in the bitmap.
  **/
  void clearAll()
  {
    for (int i = 0; i < INDEX_FROM_BIT(N); i++)
    {
      table[i] = 0;
    }
  }
  
  /**
    Sets the bit at index i
  **/
  void set(int i)
  {
    // Find the word 'i' is in.
    int idx = (int)INDEX_FROM_BIT(i);
    // And the offset.
    int off = OFFSET_FROM_BIT(i);
    // set the bit.
    table[idx] |= (0x1 << off);
  }
  
  /**
    Clears the bit at index i
  **/
  void clear(int i)
  {
    // Find the word 'i' is in.
    int idx = (int)INDEX_FROM_BIT(i);
    // And the offset.
    int off = OFFSET_FROM_BIT(i);
    // set the bit.
    table[idx] &= ~(0x1 << off);
  }
  
  /**
    Tests if the bit at index i is set.
  **/
  bool test(int i)
  {
    // Find the word 'i' is in.
    int idx = (int)INDEX_FROM_BIT(i);
    // And the offset.
    int off = OFFSET_FROM_BIT(i);
    // set the bit.
    return (table[idx] & (0x1 << off));
  }
  
  /**
    Finds the first bit that is clear. Uses optimisations so faster than
    just looping and calling test().
  **/
  int firstClear()
  {
    for (int i = 0; i < INDEX_FROM_BIT(N); i++)
    {
      if (table[i] != 0xFFFFFFFF) // nothing free, exit early.
      {
        // at least one bit is free here.
        for (int j = 0; j < 32; j++)
        {
          int toTest = 0x1 << j;
          if ( !(table[i]&toTest) )
          {
            return i*4*8+j;
          }
        }
      }
    }
    return (int)-1;
  }
  
  /**
    Finds the first bit that is set. Uses optimisations so faster than
    just looping and calling test().
  **/
  int firstSet()
  {
    for (int i = 0; i < INDEX_FROM_BIT(N); i++)
    {
      if (table[i] != 0x00000000) // nothing free, exit early.
      {
        // at least one bit is set here.
        for (int j = 0; j < 32; j++)
        {
          int toTest = 0x1 << j;
          if ( table[i]&toTest )
          {
            return i*4*8+j;
          }
        }
      }
    }
    return (int)-1;
  }
  
private:
  /**
    The bitmap itself.
  **/
  int *table;
  
  /**
    The number of bit entries
  **/
  int N;
};

#endif

